Search results for "Quantum Fourier transform"

showing 3 items of 3 documents

Any AND-OR Formula of Size N Can Be Evaluated in Time $N^{1/2+o(1)}$ on a Quantum Computer

2007

Consider the problem of evaluating an AND-OR formula on an $N$-bit black-box input. We present a bounded-error quantum algorithm that solves this problem in time $N^{1/2+o(1)}$. In particular, approximately balanced formulas can be evaluated in $O(\sqrt{N})$ queries, which is optimal. The idea of the algorithm is to apply phase estimation to a discrete-time quantum walk on a weighted tree whose spectrum encodes the value of the formula.

Discrete mathematicsQuantum t-designComputational complexity theoryGeneral Computer ScienceGeneral MathematicsSpectrum (functional analysis)Value (computer science)0102 computer and information sciencesTree (graph theory)01 natural sciencesCombinatoricsTree (descriptive set theory)Discrete time and continuous time010201 computation theory & mathematics0103 physical sciencesQuantum operationQuantum phase estimation algorithmQuantum Fourier transformQuantum walkQuantum algorithm010306 general physicsMathematicsQuantum computerSIAM Journal on Computing
researchProduct

Superlinear advantage for exact quantum algorithms

2012

A quantum algorithm is exact if, on any input data, it outputs the correct answer with certainty (probability 1). A key question is: how big is the advantage of exact quantum algorithms over their classical counterparts: deterministic algorithms. For total Boolean functions in the query model, the biggest known gap was just a factor of 2: PARITY of N inputs bits requires $N$ queries classically but can be computed with N/2 queries by an exact quantum algorithm. We present the first example of a Boolean function f(x_1, ..., x_N) for which exact quantum algorithms have superlinear advantage over the deterministic algorithms. Any deterministic algorithm that computes our function must use N qu…

FOS: Computer and information sciencesQuantum sortGeneral Computer ScienceDeterministic algorithmGeneral MathematicsFOS: Physical sciences0102 computer and information sciencesQuantum capacityComputational Complexity (cs.CC)01 natural sciences010305 fluids & plasmasCombinatorics0103 physical sciencesQuantum phase estimation algorithmQuantum informationBoolean function010306 general physicsComputer Science::DatabasesQuantum computerMathematicsDiscrete mathematicsQuantum PhysicsFunction (mathematics)Computer Science - Computational Complexity010201 computation theory & mathematicsQuantum Fourier transformNo-teleportation theoremQuantum algorithmQuantum Physics (quant-ph)Proceedings of the forty-fifth annual ACM symposium on Theory of Computing
researchProduct

Arbitrary qudit gates by adiabatic passage

2013

We derive an adiabatic technique that implements the most general SU($d$) transformation in a quantum system of $d$ degenerate states, featuring a qudit. This technique is based on the factorization of the SU($d$) transformation into $d$ generalized quantum Householder reflections, each of which is implemented by a two-shot stimulated Raman adiabatic passage with appropriate static phases. The energy of the lasers needed to synthesize a single Householder reflection is shown to be remarkably constant as a function of $d$. This technique is directly applicable to a linear trapped ion system with $d+1$ ions. We implement the quantum Fourier transform numerically in a qudit with $d=4$ (defined…

PhysicsHouseholder transformationQuantum mechanicsDegenerate energy levelsQuantum systemStimulated Raman adiabatic passageQuantum Fourier transformAdiabatic processQuantumAtomic and Molecular Physics and OpticsQuantum computerPhysical Review A
researchProduct